package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.tree.btree.TreeNode;

/**
 * ● 左子树是平衡二叉树
 * ● 右子树是平衡二叉树
 * ● | 左树高度 - 右树高度 | <= 1
 *
 * @author qidi
 * @date 2022-01-06 15:27:19
 */
class Q0110_BalancedBinaryTree {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isBalanced(TreeNode root) {
            if (root == null) return true;
            return process(root).isBalanced;
        }

        private class ReturnType {
            boolean isBalanced;
            int height;

            public ReturnType(boolean isBalanced, int height) {
                this.isBalanced = isBalanced;
                this.height = height;
            }
        }

        private ReturnType process(TreeNode node) {
            if (node == null) return new ReturnType(true, 0);

            ReturnType leftData = process(node.left);
            ReturnType rightData = process(node.right);

            // 当前树的高度
            int height = Math.max(leftData.height, rightData.height) + 1;
            // 是否平衡
            boolean isBalanced = leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height - rightData.height) <= 1;
            return new ReturnType(isBalanced, height);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0110_BalancedBinaryTree().new Solution();
    }
}